package main;

import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class CBTInserter {
    private Queue<TreeNode> queue;
    private TreeNode root;

    public CBTInserter(TreeNode root){
        this.root = root;
        this.queue = new LinkedList<>();
        this.queue.offer(root);
        while (queue.peek().left != null && queue.peek().right != null){
            TreeNode node = queue.poll();
            queue.offer(node.left);
            queue.offer(node.right);
        }
    }
    public int insert(int v){
        TreeNode parent = queue.peek();
        TreeNode node = new TreeNode(v);
        assert parent != null;
        if (parent.left == null){
            parent.left = node;
        }else {
            parent.right = node;
            queue.poll();
            queue.offer(parent.right);
        }
        return parent.val;
    }
    public TreeNode getRoot(){
        return this.root;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        CBTInserter cbtInserter = new CBTInserter(root);
        cbtInserter.insert(3);
        List<Integer> bfs = new Bfs().bfs(root);
        System.out.println(bfs);
    }
}
